package unionFound;
/**
 * 
 * @Title: CandyUnionFindImpl_v1.java 
 * @Package unionFound 
 * @Description: 并查集：QuickUnionFind
 *                  isConnected()方法是时间复杂度是O(h)级别的，h为树的高度
 *                  unionElements(p, q)时间复杂度是O(h)级别的，h为树的高度
 * @author CandyWall   
 * @date 2021年1月11日 上午11:32:18 
 * @version V1.0
 */
public class CandyUnionFindImpl implements CandyUnionFind {
    private int[] parent;
    private int[] ranks;   // ranks[i]表示以i为根的集合所表示的树的高度
    public CandyUnionFindImpl(int size) {
        parent = new int[size];
        ranks = new int[size];
        for(int i = 0; i < parent.length; i++) {
            parent[i] = i;
            ranks[i] = 1;
        }
    }

    @Override
    // 查看元素p和元素q是否所属同一个集合
    // 时间复杂度是O(h)级别的，h为树的高度
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
    
    // 查找索引为index的元素对应的集合编号（根节点索引）
    // 时间复杂度是O(h)级别的，h为树的高度
    private int find(int index) {
        checkArrayIndexRange(index);
        while(index != parent[index]) {
            parent[index] = parent[parent[index]];  // 路径压缩
            index = parent[index];
        }
        return index;
    }
    
    /**
     * 校验待操作的数组下标是否合法
     */
    private void checkArrayIndexRange(int index) {
        if(index >= parent.length || index < 0) {
            throw new IllegalArgumentException("索引index不合法！");
        }
    }

    @Override
    // 合并元素p和元素q所属的集合
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) {
            return;
        }
        // 根据两个元素所在集合所表示的树的高度不同判断合并方向
        // 将高度低的集合合并到高度高的结合上
        if(ranks[pRoot] < ranks[qRoot]) {
            parent[pRoot] = qRoot;
            // 此时树的高度仍然是以qRoot为根的集合的高度
        } else if(ranks[pRoot] > ranks[qRoot]) { 
            parent[qRoot] = pRoot;
            // 此时树的高度仍然是以pRoot为根的集合的高度
        } else { // sz[pRoot] == sz[qRoot]
            parent[qRoot] = pRoot;
            ranks[pRoot]++;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

}
